//https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/submissions/572164145/
class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        int max = 0;
        for (int i = 0; i < weights.size(); ++i)
        {
            if (weights[i] > max)
                max = weights[i];
        }
        int left = max, right = 25000000;
        while (left < right)
        {
            int mid = left + (right - left) / 2;

            int count = 0, sum = 0;
            for (int i = 0; i < weights.size(); ++i)
            {
                sum += weights[i];
                if (sum > mid) { count++; sum = weights[i]; }
                else if (sum == mid) { count++; sum = 0; }
                else continue;
            }
            if (sum) count++;
            count <= days ? right = mid : left = mid + 1;
        }
        return left;
    }
};